#include<tools_heap.h>



#define RIGHT_CHILD(x) (2*(x+1))
#define LEFT_CHILD(x) (2*x+1)
#define PARENT(x) ((x-1)/2)


static inline void swap(CHeap*ch,int index1,int index2)
{
    void* temp=malloc((ch->width));
    memmove(temp,((char*)(ch->values))+index1*ch->width,ch->width); 
    
    memmove(((char*)ch->values)+index1*ch->width,((char*)(ch->values))+index2*ch->width,ch->width);
    memmove( ((char*)ch->values)+index2*ch->width,temp,ch->width);
    
    free(temp);
}

static void adust_min(CHeap*ch,int index)
{
    int left=LEFT_CHILD(index),right=left+1;
    if(left>=ch->size)
    {
        return;
    }
    int change=left;
    if(right<ch->size&&ch->comp(((char*)ch->values)+ch->width*right,((char*)ch->values)+ch->width*left)<0)
    {
        change=right; 
    }    
    if(ch->comp(((char*)ch->values)+ch->width*change,((char*)ch->values)+ch->width*index)<0)
    {
            swap(ch,change,index);
            adust_min(ch,change);
    } 
}

void make_min_cheapi(CHeap* ch,int index)
{
    if(index>=ch->size)
    {
        return ;
    }
    int left=LEFT_CHILD(index),right=left+1;
    make_min_cheapi(ch,left);
    make_min_cheapi(ch,right);
    adust_min(ch,index);
}

static void make_min_cheap(CHeap*ch)
{
    for(int i=ch->size/2-1;i>=0;i--)
    {
        adust_min(ch,i);
    }
}



static void adust_max(CHeap*ch,int index)
{
    int left=LEFT_CHILD(index),right=left+1;
    if(left>=ch->size)
    {
        return;
    }
    int change=left;
    if(right<ch->size&&ch->comp(((char*)ch->values)+ch->width*right,((char*)ch->values)+ch->width*left)>0)
    {
        change=right; 
    }    
    if(ch->comp(((char*)ch->values)+ch->width*change,((char*)ch->values)+ch->width*index)>0)
    {
            swap(ch,change,index);
            adust_max(ch,change);
    } 
}
void make_max_cheapi(CHeap* ch,int index)
{
    if(index>=ch->size)
    {
        return ;
    }
    int left=LEFT_CHILD(index),right=left+1;
    make_max_cheapi(ch,left);
    make_max_cheapi(ch,right);
    adust_max(ch,index);
}

static void make_max_cheap(CHeap*ch)
{
    for(int i=ch->size/2-1;i>=0;i--)
    {
        adust_max(ch,i);
    }
}

void make_cheap(CHeap*ch)
{
    if(ch->mark==0)
    {
        make_min_cheap(ch);
    }
    else
    {
        make_max_cheap(ch);
    }
}

void* pop_cheap(CHeap*ch)
{
    if(ch->size<=0)
    {
        return NULL;
    }
    ch->size--;
    void*re=(void*)malloc(ch->width);
    memcpy(re,ch->values,ch->width);
    memset(ch->values,0,sizeof(ch->width)); 
    swap(ch,ch->size,0);
    if(ch->mark==0)
    {
        adust_min(ch,0);
    }
    else
    {
        adust_max(ch,0);
    }
    return re;
}

static void adust_parent_min(CHeap*ch,int index)
{
    int pa=PARENT(index);
    if(pa>=0&&ch->comp(((char*)ch->values)+ch->width*pa,((char*)ch->values)+ch->width*index)>0)
    {
        swap(ch,index,pa);
        adust_parent_min(ch,pa);
    } 
}

static void adust_parent_max(CHeap*ch,int index)
{
    int pa=PARENT(index);
    if(pa>=0&&ch->comp( ((char*)ch->values)+ch->width*pa, ((char*)ch->values)+ch->width*index)<0)
    {
        swap(ch,index,pa);
        adust_parent_max(ch,pa);
    } 
}
void insert_cheap(CHeap*ch,void* value)
{
    if(ch->size>=ch->max_size){return;}
    memcpy(((char*)ch->values)+ch->width*ch->size,value,ch->width); 
    ch->mark==0?adust_parent_min(ch,ch->size):adust_parent_max(ch,ch->size);
    ch->size++;
}
